package com.wcj.test;

/**
 * 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，
 * 长度为n，反转该链表后，返回新链表的表头。
 *
 * 数据范围： 0\leq n\leq10000≤n≤1000
 * 要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
 */

import com.wcj.linktable.ListNode;

public class 反转链表 {


    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curHead = head.next;
        ListNode rucTail = head;
        rucTail.next = null;
        while (curHead != null) {
            ListNode tmp = curHead;
            curHead = curHead.next;
            tmp.next = rucTail;
            rucTail = tmp;
        }
        return rucTail;
    }
}
